package momental;

import array.ListNode;

/**
 * Created by fengliejv on 2022/1/18.
 */
public class Solution {
    public ListNode solution3(ListNode node, int k) {
        ListNode quick = node;
        ListNode slow = node;
        while (k-- != 0 && quick!= null) {
            quick = quick.next;
        }
        if(quick==null){
            return node.next;
        }
        while (quick.next != null) {
            quick = quick.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return node;
    }


    public int solution2(int[] input, int target) {
        int begin = 0;
        int end = input.length - 1;
        int max_index = solution(input);
        int result = binarySearch(input, target, 0, max_index, true);
        if (result != -1) {
            return result;
        } else {
            result = binarySearch(input, target, max_index, end, false);
        }
        return result;
    }

    public int binarySearch(int[] input, int target, int begin, int end, boolean up) {
        int start = begin;
        int en = end;
        while (start != en) {
            int mid = (start + en) / 2;
            if (input[mid] == target) {
                return mid;
            }
            if(up){
                if (input[mid] > target) {
                    en = mid - 1;
                } else {
                    start = mid + 1;
                }
            }else {
                if(input[mid]>target){
                    start=mid+1;
                }else {
                    en=mid-1;
                }
            }
        }
        return -1;
    }


    public int solution(int[] input) {
        int begin = 0;
        int end = input.length - 1;
        while (begin != end) {
            int mid = (end - begin) / 2 + begin;
            if (mid == 0 || mid == input.length) {
                return mid;
            }
            if (input[mid] > input[mid - 1] && input[mid] > input[mid + 1]) {
                return mid;
            }
            if (input[mid] > input[mid + 1] && input[mid] < input[mid - 1]) {
                end = mid - 1;
            } else {
                begin = mid + 1;
            }
        }
        return -1;
    }
}
